package org.algorithm.熊猫.回溯算法;

import org.junit.Test;

import java.util.List;

/**
 * 编写一个程序，通过填充空格来解决数独问题。
 * <p>
 * 数独的解法需 遵循如下规则：
 * <p>
 * 数字1-9在每一行只能出现一次。
 * 数字1-9在每一列只能出现一次。
 * 数字1-9在每一个以粗实线分隔的3x3宫内只能出现一次。（请参考示例图）
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/sudoku-solver
 */
public class $4月28日$解数独 {

    @Test
    public void test(){
        char[][] arr =new char[][]{{'5','3','.','.','7','.','.','.','.'},{'6','.','.','1','9','5','.','.','.'},{'.','9','8','.','.','.','.','6','.'},{'8','.','.','.','6','.','.','.','3'},{'4','.','.','8','.','3','.','.','1'},{'7','.','.','.','2','.','.','.','6'},{'.','6','.','.','.','.','2','8','.'},{'.','.','.','4','1','9','.','.','5'},{'.','.','.','.','8','.','.','7','9'}};
        solveSudoku(arr);
        System.out.println(arr);
    }

    public void solveSudoku(char[][] board) {
        backTrack(board, 0, 0);
    }

    private boolean backTrack(char[][] board, int i, int j) {
        int m = 9, n = 9;
        if (j == n) {
            return backTrack(board, i + 1, 0);
        }
        if (i == m) {
            // 找到⼀个可⾏解，触发 base case
            return true;
        }

        if (board[i][j] != '.') {
            // 如果有预设数字，不⽤我们穷举
            return backTrack(board, i, j + 1);
        }
        for (char ch = '1'; ch <= '9'; ch++) {
            // 如果遇到不合法的数字，就跳过
            if (!isValid(board, i, j, ch))
                continue;
            board[i][j] = ch;
            // 如果找到⼀个可⾏解，⽴即结束
            if (backTrack(board, i, j + 1)) {
                return true;
            }
            board[i][j] = '.';
        }
        // 穷举完 1~9，依然没有找到可⾏解，此路不通
        return false;
    }

    private boolean isValid(char[][] board, int i, int j, char ch) {
        for (int index = 0; index < 9; index++) {
            //判断行
            if (board[i][index] == ch) return false;
            //判断列
            if(board[index][j]==ch)return false;
            //判断3*3
            if (board[(i/3)*3 + index/3][(j/3)*3 + index%3] == ch)
                return false;
        }
        return true;
    }
}
